/*
 * Author: 肖思佳 1300012872
 *
 * Outline:
 * 对于每个query，枚举所有的tag，利用人与人之间的认识关系，
 * 广度优先搜索找到图中很多的联通块，联通块中所有的人都含有
 * 这个tag而且生日在某个指定日期之后，找到其中最大的联通块
 * 作为这个tag的标记值，将标记值排序输出前面几个即可。
 * 这样的做法复杂度是O(num_query * num_tag * num_relation)，
 *
 * Optimization:
 * 无。
 *
 * Performance：
 * 跑1k的数据大概要花费9秒。
 */
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <map>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>

using namespace std;

#define LENGTH 1000							//输入长度
#define SCALE 10000

string birthday_limit;
int ans_num;

char buf[LENGTH];									//用于读写文件的操作
string data_path;
int data_size;
string query_file;
string answer_file;

map<int, int> personID; int count_person = 0;		//person_ID的离散化
map<int, string> tag;								//把tag标号对应到字符串
vector<int> tag_key; int tag_key_num = 0;			//tag有哪些数字编号	
vector<int> person_has_interest[SCALE];				//每个人的兴趣爱好
map<int, string> person_birthday;					//生日

vector<vector<int> > relation;
vector<int> visit;


void get_personID_and_birthday()
{
	string person_data_file = data_path + "person.csv";               //读取personID并离散化;读取生日信息
	FILE *f_person = fopen(person_data_file.c_str(), "r");


	fgets(buf, LENGTH, f_person);
	while(fgets(buf, LENGTH, f_person) != NULL)
	{
		int i = 0;
		string tmp;
		while(1)
		{
			if(buf[i] == '|') { i++; break;}
			tmp += buf[i];
			i++;
		}
		personID[atoi(tmp.c_str())] = ++count_person;								//count_person 从1开始
		int count_seg = 1;											//读取birthday
		while(1)
		{
			if(count_seg == 4) break;
			if(buf[i] == '|') count_seg++;
			i++;
		}
		tmp = "";
		while(1)
		{
			if(buf[i] == '|') break;
			tmp += buf[i];
			i++;
		}
		person_birthday[count_person] = tmp;
	}


	fclose(f_person);
}

void get_tag()
{
	string tag_data_file = data_path + "tag.csv";               //读取tag
	FILE *f_tag = fopen(tag_data_file.c_str(), "r");

	fgets(buf, LENGTH, f_tag);
	tag_key.push_back(0);

	while(fgets(buf, LENGTH, f_tag) != NULL)
	{
		string tmp1, tmp2;										//	tmp1: tag的数字编号 tmp2：tag的名称
		int i = 0;
		while(1)
		{
			if(buf[i] == '|') { i++; break;}
			tmp1 += buf[i]; i++;
		}
		while(1)
		{
			if(buf[i] == '|') break;
			tmp2 += buf[i]; i++;
		}
		
		tag_key.push_back(atoi(tmp1.c_str()));
		tag[++tag_key_num] = tmp2;
	}

	fclose(f_tag);
}

void add_edge(int a, int b)										//人相互认识则连边
{
	relation[a].push_back(b);
}

void get_person_relation()
{
	relation.resize(count_person + 10);

	string person_knows_person_data_file = data_path + "person_knows_person.csv";               //person knows person
	FILE *f_person_knows_person = fopen(person_knows_person_data_file.c_str(), "r");
	int tmp1, tmp2;
	fgets(buf, LENGTH, f_person_knows_person);
	while(fscanf(f_person_knows_person, "%d|%d", &tmp1, &tmp2) != EOF)
	{
		add_edge(personID[tmp1], personID[tmp2]);
	}
	fclose(f_person_knows_person);
}

void get_person_interest()
{
	string person_hasInterest_tag_data_file = data_path + "person_hasInterest_tag.csv";               //person's interest
	FILE *f_person_hasInterest_tag = fopen(person_hasInterest_tag_data_file.c_str(), "r");
	int tmp1, tmp2;
	fgets(buf, LENGTH, f_person_hasInterest_tag);
	while(fscanf(f_person_hasInterest_tag, "%d|%d", &tmp1, &tmp2) != EOF)
	{
		person_has_interest[personID[tmp1]].push_back(tmp2);
	}
	fclose(f_person_hasInterest_tag);

}

bool valid_birthday(int personID)
{
	return person_birthday[personID] >= birthday_limit;					
}

int has_tag(int personID, int tag)
{
	int range = (int)person_has_interest[personID].size();
	for(int i = 0; i < range; i++)
		if(person_has_interest[personID][i] == tag_key[tag]) return true;
	return false;
}

struct Ctag
{
	int key, num;
	bool operator < (const Ctag b) const
	{ 
		if(num == b.num) return tag[key] < tag[b.key];
		return num > b.num; 
	}

} *count_tag;

queue<int> q;

void find_answer()
{
	count_tag = new Ctag[tag_key_num + 10];

	for(int i = 1; i <= tag_key_num; i++)
		count_tag[i].key = i, count_tag[i].num = 0;

	visit.resize(count_person + 10);

	for(int tag = 1; tag <= tag_key_num; tag++)
	{
		for(int i = 1; i <= count_person; i++)
			visit[i] = 0;

		int count = 0;
		for(int i = 1; i <= count_person; i++)
			if(valid_birthday(i) && has_tag(i, tag) && !visit[i])
			{
				count = 1, q.push(i), visit[i] = 1;
				while(!q.empty())
				{
					int tmp = q.front(); q.pop();
					for(int i = 0; i < (int)relation[tmp].size(); i++)
					{
						int u = relation[tmp][i];
						if(valid_birthday(u) && has_tag(u, tag) && !visit[u])
							q.push(u), count++, visit[u] = 1;
					}
				}

				if(count > count_tag[tag].num)
					count_tag[tag].num = count;
			}
	}
}

void handle_query(char s[])
{
    int len = sscanf(s, "%d", &ans_num);
    birthday_limit = string(s + len + 1);
	/*for(int i = 0; i < (int)strlen(s); i++)
	{
		string tmp;
		if(s[i] == '(')
		{
			i++;
			while(s[i] != ',')
				tmp += s[i], i++;
			ans_num = atoi(tmp.c_str());

			i += 2;
			while(s[i] != ')')
				birthday_limit += s[i], i++;
			break;
		}
	}*/
}

int main(int argc, char *argv[])
{
#ifndef LOCAL
	data_path = argv[1];
	data_size = atoi(argv[2]);
	query_file = argv[3];
	answer_file = argv[4];
#else
    data_path = "../../../data/1k-network/";
    data_size = 1000;
    query_file = "../query2.in";
    answer_file = "../query2.out";
#endif

	get_personID_and_birthday();
	get_tag();
	get_person_relation();
	get_person_interest();

	FILE *f_query = fopen(query_file.c_str(), "r");
	FILE *f_answer = fopen(answer_file.c_str(), "w");

	while(fgets(buf, LENGTH, f_query) != NULL)
	{
        buf[strlen(buf) - 1] = '\0';
		birthday_limit = "";
		handle_query(buf);
		find_answer();

		sort(count_tag + 1, count_tag + tag_key_num + 1);
		for(int i = 1; i <= ans_num; i++)
			fprintf(f_answer, "%s ", tag[count_tag[i].key].c_str());
		fprintf(f_answer, "\n");

		delete [] count_tag;
	}

	fclose(f_query);
	fclose(f_answer);

	return 0;
}
